This invention relates generally to circuits and computational methods for obtaining an approximation to a base 2 logarithm of a binary number and, more particularly, to a circuits and methods for a fast approximation implemented with few components or embedded gate resources.
Logarithms appear in calculations in diverse fields ranging from audio to radar and also are used to facilitate computation. Due to the widespread use of logarithms in a calculation and computation, several methods and circuits have been proposed for approximating a logarithm of a binary input. However, previously available methods and circuits either require multipliers, which would render the calculation slower, requiring more cycles of processing time, or require a large number of elements, which would render the implementation as a circuit or integrated circuit costly.
Since converting from a logarithm of one base to a logarithm of another base only requires multiplying by scaling factor, no generality is lost by developing an approximation only for the base 2 logarithm of a binary input. The logarithm of an input number consists of an integer part, sometimes called the characteristic, and a fractional part, sometimes called the mantissa. For a binary input number, the integer part of the base 2 logarithm is equal to the number of bits down from the most significant bit. For example, for a hexadecimal input of 8FF0, corresponding to a binary input of 1000111111110000, there are 15 bits after the most significant bit. Therefore, the integer part of the base 2 logarithm is 15 or binary 1111 or hexadecimal F. Since the integer part of the base 2 logarithm of a binary input is so easily defined, a barrel shifter implementation has been used. Approximating the mantissa requires more effort.
In U.S. Pat. No. 5,801,974 (Park, Sep. 1, 1998), Park utilizes a multiplier, two adders and a shifter to obtain an approximation to the mantissa. In U.S. Pat. Nos. 5,629,884, 5,642,305 and 5,703,801 (Pan et al., May 13, 1997, Jun. 24, 1997, and Dec. 20, 1997, respectively), designs for an approximating circuit are disclosed comprising a memory, a multiplier unit and other components. In U.S. Pat. No. 5,365,465 (Larson, Nov. 15, 1994), U.S. Pat. No. 5,600,581 (Dworkin et al., Feb. 4, 1997), U.S. Pat. No. 5,831,878 (Ichida, Nov. 3, 1998) designs for an approximating circuit are disclosed comprising at least one multiplier unit.
For many applications, such as those performing real time calculations and/or implementing the approximation for use with a digital signal processor (DSP), the use of multipliers can result in additional required cycles of processing time to complete the calculation.
A design for a logarithm approximating circuit not utilizing multipliers is disclosed by Windsor et al. in U.S. Pat. No. 4,078,250 (Mar. 7. 1978). However, that design requires two lookup tables with 1024 entries each for 16 bit input, an adder and a subtractor as well as other components.
There is a need for a logarithm approximating circuit that occupies a small footprint (has fewer elements requiring fewer gates) and takes minimal hardware computation cycles.